#include <iostream>
/*
问题：01背包问题
描述：背包承重weight，物品个数n，物品i的重量w[i],价值val[i]
解法：动态规划
首先：得确定状态，就是子问题和原问题的变量，每个物品的重量和价值都不变，
变量不是背包的承重，背包的承重是不变的，变量应该是背包剩余的承重空间，以及剩下的可以选的物品
所以说这里的变量有俩个
dp[i][w]表示：对于前i个物品，当背包容量为w时，可以装的最大价值dp[i][w]
base case: dp[i][0] = 0; dp[0][w] = 0;需要计算dp[n][w] = ?

状态转移方程：
怎么选择？当然是0-1选择啦？一个物品要么选择，要么不选择。
在w的容量约束下，把物品i装进背包的最大价值是多少？=> val[i] + dp[i-1][w-wt[i]]
在w的容量约束下，不把物品i装进背包的最大价值是多少？ => dp[i-1][w]
比较上面俩个值。

*/

int backpack01(int weight, int n, int wt[], int val[])
{
    int dp[n+1][weight+1];
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= weight; j++)
            dp[i][j] = 0;
    }
    for (int i = 1; i <= n; i++)  //因为dp[i][0] = dp[0][w] = 0都已经初始化为0了。
    {
        for (int w = 1; w <= weight; w++)
        {
            if (w - wt[i - 1] < 0)  //判断第i个物品能不能装进去，第i个物品的序号i-1
            {
                //装不进去
                dp[i][w] = dp[i-1][w];
            }
            else
            {   
                //第i个物品装进去的价值，第i个物品的价值时val[i - 1],重量是wt[i-1]
                int p = dp[i - 1][w - wt[i - 1]] + val[i - 1];
                int q = dp[i - 1][w];
                dp[i][w] = p > q ? p : q;
            }
        }
    }
    return dp[n][weight];
}
int main()
{
    using namespace std;
    int weight = 1;
    int n = 3;
    int w[3] = {2, 1, 3};
    int val[3] = {4, 2, 3};
    cout << backpack01(weight, n, w, val) << endl;
    return 0;
}

